package classic;

/**
 * 求数组中重复次数过半的元素，如数组为：
 * {3,4,3,3,4,4,3,5,3}，则该元素为3
 *
 * @author zj
 */
public class OverHalfElementsInArray {

    public static void main(String[] args) {
        int arr[] = {3, 4, 3, 3, 4, 4, 3, 5, 3};
        System.out.println(find(arr));
    }

    /**
     * 遍历数组，保存两个值，一个是数组中的一个数字，一个是次数，
     * 当遍历下一个数字时，如果下一个数与之前保存的数相同，则次数加1，否则减1；
     * 如果次数为0了，则保存下一个数字，并重置次数为1
     *
     * @param A
     * @return
     */
    public static int find(int A[]) {
        int result = A[0];
        int count = 1;
        for (int i = 1; i < A.length; i++) {
            if (count == 0) {
                result = A[i];
                count = 1;
            } else if (A[i] == result) {
                count++;
            } else if (A[i] != result) {
                count--;
            }
        }
        return result;
    }
}
